package com.example.algo.lru;

import java.util.HashMap;
import java.util.Map;

/**
 * 简单的 LRU 算法实现
 */
public class SimpleLru {

    private Node head; // 头结点
    private Node tail; // 尾结点

    private Map<String, Node> nodeHashMap;
    private int capacity;

    public SimpleLru(int capacity) {
        this.capacity = capacity;
        nodeHashMap = new HashMap<String, Node>(capacity);
        tail = new Node();
        head = new Node();
        head.next = tail;
        tail.prev = head;
    }

    public String get(String key) {
        Node node = nodeHashMap.get(key);
        if (node == null) {
            return null;
        }
        // 访问一次刷新一次位置，key 移动到链表头位置
        moveNodeToHead(node);
        return node.value;
    }

    public void put(String key, String value) {
        Node node = nodeHashMap.get(key);

        if (node != null) {
            node.value = value;
            moveNodeToHead(node);
            return;
        }

        // 容量达到阈值，需要进行淘汰数据
        if (nodeHashMap.size() >= capacity) {
            // 淘汰尾部节点
            removeNode(tail);
            // 移除 map 中的索引
            nodeHashMap.remove(tail.key);
        }

        node = new Node(key, value);
        nodeHashMap.put(key, node);
        addNodeToHead(node);

    }

    /**
     * 删除节点
     */
    private void removeNode(Node node) {
        if (node == tail) {
            tail = tail.prev;
            tail.next = null;
        } else if (node == head) {
            head = head.next;
            head.prev = null;
        } else {
            node.prev.next = node.next;
            node.next.prev = node.prev;
        }
    }

    /**
     * 将 node 添加到头节点的位置
     *
     * @param node
     */
    private void addNodeToHead(Node node) {
        node.next = head.next;
        head.next.prev = node;
        node.prev = head;
        head.next = node;
    }

    /**
     * 将 node 移动到头部
     *
     * @param node
     */
    private void moveNodeToHead(Node node) {
//        // 方式一: 先删除 再添加
//        removeNode(node);
//        addNodeToHead(node);


        // 方式二: 直接移动节点
        node.prev.next = node.next;
        node.next.prev = node.prev;

        head.next.prev = node;
        node.next = head.next;
        head.next = node;
        node.prev = head;
    }


    class Node {
        private String key;
        private String value;
        private Node prev;
        private Node next;

        public Node() {
        }

        public Node(String key, String value) {
            this.key = key;
            this.value = value;
        }
    }

    private void print(Node node) {
        while (node.next != null) {
            System.out.print(node.value + "->");
            node = node.next;
        }
        System.out.println();
    }

    public static void main(String[] args) {

        SimpleLru lru = new SimpleLru(3);
        lru.put("1", "1");
        lru.put("2", "2");
        lru.put("3", "3");
        // 应该输出 3 2 1
        lru.print(lru.head);

        // 容器已满
        lru.put("4", "4");
        // 应输出 4 3 2
        lru.print(lru.head);

        // 访问最后一个元素，访问之后应该添加队列头部
        String s = lru.get("2");
        System.out.println("访问链表最后一个元素 --> " + s);
        // 应输出 2 4 3
        lru.print(lru.head);

        // 再添加一个
        lru.put("5", "5");
        // 应输出 5 2 4
        lru.print(lru.head);


    }

}
